package com.yxp.offer;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * @Auther : yxpweb
 * @Date : 2021/4/29 9:16
 * @Description: 剑指 Offer 50. 第一个只出现一次的字符
 */
public class Problem50 {
    public static void main(String[] args) {
        System.out.println(firstUniqChar2("ccaccaf"));
    }

    /**
     * 队列
     *
     * @param s
     * @return
     */
    public static char firstUniqChar(String s) {
        if (s.length() == 0) {
            return ' ';
        }
        Set<String> set = new HashSet<>();
        LinkedList linkedList = new LinkedList<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            String temps = String.valueOf(chars[i]);
            if (!set.contains(temps)) {
                set.add(temps);
                linkedList.addLast(temps);
            } else {
                linkedList.remove(temps);
            }
        }
        if(linkedList.isEmpty()){
            return ' ';
        }
        return linkedList.getFirst().toString().toCharArray()[0];
    }

    /**
     * 使用哈希表存储索引
     * @param s
     * @return
     */
    public static char firstUniqChar2(String s) {
        Set<Character> set = new HashSet<>();
        char[] chars = s.toCharArray();
        char resultChar = ' ';
        for (int i = 0; i < chars.length; i++) {
            if(set.contains(chars[i])){
                continue;
            }
            resultChar = chars[i];
            for (int j = i + 1; j < chars.length; j++) {
                if(resultChar == chars[j]){
                    resultChar = ' ';
                    set.add(chars[i]);
                    break;
                }
            }
            if(resultChar != ' '){
                return resultChar;
            }
        }
        return resultChar;
    }
}
